Stack (abstract data type)

Why it exists

Many tasks need to remember things in the order they were met and then deal with the most recent one first: undoing the last edit, going back through the pages you visited, matching the most recently opened bracket, returning from the function that was called last. A stack gives exactly this behaviour and nothing more. Restricting yourself to one end is what makes the structure fast (every operation is constant time) and easy to reason about.

Prerequisites

Precise definitions

• Abstract data type (ADT). A description of what a structure does (its operations and their rules), not how it is stored. A stack can be built on an array or on a linked list; the user of the ADT does not care.
• Stack. A collection in which items are added and removed only at one end, called the top. The item removed is always the one added most recently: LIFO (last in, first out).
• Operations.

• Overflow. push on a full (array) stack. Underflow. pop or peek on an empty stack. A correct implementation checks for both.
• Array implementation. Keep the items in s[0 .. N-1] and an integer top. This page uses the most common convention:
  • top = -1 means empty. push(x) is s[++top] = x. pop() is return s[top--].
  • The number of items is top + 1. The stack is full when top == N - 1.
• The other convention. Some books (K&R's calculator, for instance, keeps sp this way) keep top as "the index of the next free cell": top = 0 means empty, push(x) is s[top++] = x, pop() is return s[--top], the number of items is top, and the stack is full when top == N. Both are correct. A GATE question that shows code or gives the starting value of top tells you which one applies. Never mix them.
• Linked implementation. Each item is a node. push inserts a new node at the head and pop removes the head node. No fixed size, no overflow (until memory runs out). See linked lists.

How it works

The animation below runs a real stack made of an array s[5] and an index top. Step through it and watch two things:

1. push first changes top, then writes the cell. pop first reads the cell, then changes top.
2. pop does not erase anything. After the first pop the 30 is still in s[2]; it is just no longer part of the stack, and the next push overwrites it.

Which output orders can a stack produce?

Suppose the numbers $1, 2, \ldots, n$ are pushed in that order, but pops may be interleaved with pushes in any way. The numbers come out in some order. Which orders are possible?

• Take any output order. If, for some three numbers $a < b < c$, it prints $c$ first, then $a$, then $b$, the order is impossible. (To print $c$ first, $a$ and $b$ must already be on the stack with $b$ above $a$, so $b$ would come out before $a$.) This is the forbidden pattern "3 1 2".
• The number of possible orders is the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$: 1, 2, 5, 14, 42 for $n = 1, \ldots, 5$.
• To test one particular order, simulate it: to print the next wanted number, keep pushing input numbers until it is on top, then pop it. If it is buried under another number, the order is impossible.

Worked examples

#include <stdio.h>
 
#define N 4
 
static int s[N];
static int top = -1;
 
static int push(int x) {
    if (top == N - 1) return 0;
    s[++top] = x;
    return 1;
}
 
static int pop(int *x) {
    if (top == -1) return 0;
    *x = s[top--];
    return 1;
}
 
int main(void) {
    int x;
    for (int v = 1; v <= 5; v++)
        printf("push %d %s\n", v * 10, push(v * 10) ? "ok" : "overflow");
    while (pop(&x)) printf("%d ", x);
    printf("\n%s\n", pop(&x) ? "popped" : "underflow");
    return 0;
}

push 10 ok
push 20 ok
push 30 ok
push 40 ok
push 50 overflow
40 30 20 10
underflow

#include <stdio.h>
 
int main(void) {
    int s[10], top = -1;
    s[++top] = 1;
    s[++top] = 2;
    printf("%d ", s[top--]);
    s[++top] = 3;
    s[++top] = 4;
    printf("%d ", s[top--]);
    printf("%d ", s[top--]);
    s[++top] = 5;
    printf("%d ", s[top--]);
    printf("%d\n", s[top--]);
    return 0;
}

2 4 3 5 1

#include <stdio.h>
 
static int valid(const int *p, int n) {
    int st[8], top = -1, next = 1;
    for (int i = 0; i < n; i++) {
        while (top < 0 || st[top] != p[i]) {
            if (next > n) return 0;
            st[++top] = next++;
        }
        top--;
    }
    return 1;
}
 
static int count(int *p, int used, int n, int k) {
    if (k == n) return valid(p, n);
    int c = 0;
    for (int v = 1; v <= n; v++) {
        if (used & (1 << v)) continue;
        p[k] = v;
        c += count(p, used | (1 << v), n, k + 1);
    }
    return c;
}
 
int main(void) {
    int p[8];
    int a[4] = {3, 1, 2, 4}, b[4] = {2, 1, 4, 3};
    int c4 = count(p, 0, 4, 0);
    int c5 = count(p, 0, 5, 0);
    int va = valid(a, 4);
    int vb = valid(b, 4);
    printf("%d %d %d %d\n", c4, c5, va, vb);
    return 0;
}

14 42 0 1

#include <stdio.h>
 
#define N 6
 
static int a[N];
static int t1 = -1, t2 = N;
 
static int push1(int x) {
    if (t1 + 1 == t2) return 0;
    a[++t1] = x;
    return 1;
}
 
static int push2(int x) {
    if (t1 + 1 == t2) return 0;
    a[--t2] = x;
    return 1;
}
 
int main(void) {
    push1(1);
    push1(2);
    push1(3);
    push1(4);
    push2(9);
    push2(8);
    int r = push1(5);
    printf("%d %d %d %d\n", t1, t2, r, (t1 + 1) + (N - t2));
    return 0;
}

3 4 0 6

#include <stdio.h>
#include <string.h>
 
int main(void) {
    const char *in = "GATE";
    char st[16];
    int top = -1;
    for (size_t i = 0; i < strlen(in); i++) st[++top] = in[i];
    while (top >= 0) putchar(st[top--]);
    putchar('\n');
    return 0;
}

ETAG

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
};
 
static struct node *top;
 
static void push(int x) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) exit(1);
    n->data = x;
    n->next = top;
    top = n;
}
 
static int pop(void) {
    struct node *n = top;
    int x = n->data;
    top = n->next;
    free(n);
    return x;
}
 
int main(void) {
    push(1);
    push(2);
    push(3);
    int a = pop();
    int b = pop();
    int c = pop();
    printf("%d %d %d\n", a, b, c);
    return 0;
}

3 2 1

Cheat box

Traps and GATE patterns

Connections

Function calls use a stack: each call pushes an activation record and each return pops it (recursion and the call stack, and the compiler's activation records). The next topic, stack applications, uses the structure for bracket matching, expression conversion and evaluation. The opposite discipline is the queue: first in, first out.

PYQs

Consider a stack S and a queue Q. Both of them are
initially empty and have the capacity to store ten
elements each. The elements 1,2,3,4, and 5 arrive
one by one, in that order. When an element arrives,
it is assigned either to S (pushed on S ) or to Q
(enqueued to Q ). Once all the five elements are
stored, the output is generated in two steps. First,
stack S is emptied by popping all elements. Then
queue Q is emptied by dequeueing all elements.
The output obtained by following this process is
43125 .
Given the output, the objective is to predict whether
an element was assigned to S or Q.
Which of the following options is/are possible valid
assignment(s) of the elements?
Note: In the options, the notation xS denotes that
element x was assigned to S and yQ denotes that
element y was assigned to Q.

Consider the following sequence of operations on
an empty stack.
push(54); push(52); pop(); push(55); push(62); s =
pop();
Consider the following sequence of operations on
an empty queue.
enqueue (21); enqueue (24); dequeue (); enqueue
(28); enqueue (32); q = dequeue();
The value of s +q is
.
We maintain exactly two external pointers FRONT
and REAR pointing to the front node and the rear
node of the queue, respectively. Which of the
following statements is/are CORRECT for such a
circular queue, so that insertion and deletion
operations can be performed in O(1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

Let Q denote a queue containing sixteen numbers and
S be an empty stack. Head(Q) returns the element at
the head of the queue Q without removing it from Q.
Similarly Top(S) returns the element at the top of S
without removing it from S. Consider the algorithm
given below.

Consider the C program below
#include <stdio.h>
int *A, stkTop;
int stkFunc (int opcode, int val)
{
static int size=0, stkTop=0;
switch (opcode) {
case -1: size = val; break;
case 0: if (stkTop< size )
A[stkTop++]=val; break;
default: if (stkTop) return A[--stkTop];
}
return -1;
}
int main()
{
int B[20]; A=B; stkTop = -1;
stkFunc (-1, 10);
stkFunc (0, 5);
stkFunc (0, 10);
printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0));
}
The value printed by the above program is

.

Suppose a stack implementation supports an
instruction REVERSE, which reverses the order of
elements on the stack, in addition to the PUSH and
POP instructions. Which one of the following
statements is TRUE (with respect to this modified
stack)?

An implementation of a queue Q, using two stacks
S1 and S2, is given below:
void insert (Q, x) {
push(S1, x);

An Abstract Data Type (ADT) is:

Self-check

Revision card

References