Top List Top

Which operation of stack returns the topmost element of the stack?

Non-essential operationsEdit

In many implementations, a stack has more operations than the essential "push" and "pop" operations. An example of a non-essential operation is "top of stack", or "peek", which observes the top element without removing it from the stack.[17] This could be done with a "pop" followed by a "push" to return the same data to the stack, so it is not considered an essential operation. If the stack is empty, an underflow condition will occur upon execution of either the "stack top" or "pop" operations. Additionally, many implementations provide a check if the stack is empty and one that returns its size.

Software stacksEdit

ImplementationEdit

A stack can be easily implemented either through an array or a linked list. What identifies the data structure as a stack, in either case, is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations. The following will demonstrate both implementations, using pseudocode.

ArrayEdit

An array can be used to implement a [bounded] stack, as follows. The first element, usually at the zero offset, is the bottom, resulting in array[0] being the first element pushed onto the stack and the last element popped off. The program must keep track of the size [length] of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted [assuming a zero-based index convention]. Thus, the stack itself can be effectively implemented as a three-element structure:

structure stack: maxsize: integer top: integer items: array of item procedure initialize[stk: stack, size: integer]: stk.items ← new array of size items, initially empty stk.maxsize ← size stk.top ← 0

The push operation adds an element and increments the top index, after checking for overflow:

procedure push[stk: stack, x: item]: if stk.top = stk.maxsize: report overflow error else: stk.items[stk.top] ← x stk.top ← stk.top + 1

Similarly, pop decrements the top index after checking for underflow, and returns the item that was previously the top one:

procedure pop[stk: stack]: if stk.top = 0: report underflow error else: stk.top ← stk.top − 1 r ← stk.items[stk.top] return r

Using a dynamic array, it is possible to implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array, which is a very efficient implementation of a stack since adding items to or removing items from the end of a dynamic array requires amortized O[1] time.

Linked listEdit

Another option for implementing stacks is to use a singly linked list. A stack is then a pointer to the "head" of the list, with perhaps a counter to keep track of the size of the list:

structure frame: data: item next: frame or nil structure stack: head: frame or nil size: integer procedure initialize[stk: stack]: stk.head ← nil stk.size ← 0

Pushing and popping items happens at the head of the list; overflow is not possible in this implementation [unless memory is exhausted]:

procedure push[stk: stack, x: item]: newhead ← new frame newhead.data ← x newhead.next ← stk.head stk.head ← newhead stk.size ← stk.size + 1 procedure pop[stk: stack]: if stk.head = nil: report underflow error r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 return r

Stacks and programming languagesEdit

Some languages, such as Perl, LISP, JavaScript and Python, make the stack operations push and pop available on their standard list/array types. Some languages, notably those in the Forth family [including PostScript], are designed around language-defined stacks that are directly visible to and manipulated by the programmer.

The following is an example of manipulating a stack in Common Lisp [">" is the Lisp interpreter's prompt; lines not starting with ">" are the interpreter's responses to expressions]:

> [setf stack [list 'a 'b 'c]] ;; set the variable "stack" [A B C] > [pop stack] ;; get top [leftmost] element, should modify the stack A > stack ;; check the value of stack [B C] > [push 'new stack] ;; push a new top onto the stack [NEW B C]

Several of the C++ Standard Library container types have push_back and pop_back operations with LIFO semantics; additionally, the stack template class adapts existing containers to provide a restricted API with only push/pop operations. PHP has an SplStack class. Java's library contains a Stack class that is a specialization of Vector. Following is an example program in Java language, using that class.

import java.util.Stack; class StackDemo { public static void main[String[]args] { Stack stack = new Stack[]; stack.push["A"]; // Insert "A" in the stack stack.push["B"]; // Insert "B" in the stack stack.push["C"]; // Insert "C" in the stack stack.push["D"]; // Insert "D" in the stack System.out.println[stack.peek[]]; // Prints the top of the stack ["D"] stack.pop[]; // removing the top ["D"] stack.pop[]; // removing the next top ["C"] } }

Stack and its basic Operations

What is stack?

First, let us see the properties of data structures that we already do know and build-up our concepts towards the stack.

Array: Its a random-access container, meaning any element of this container can be accessed instantly
Linked List: It's a sequential-access container, meaning that elements of this data structure can only be accessed sequentially

→ Following a similar definition, a stack is a container where only the top element can be accessed or operated upon.

A Stack is a data structure following the LIFO[Last In, First Out] principle.

If you have trouble visualizing stacks, just assume a stack of books.

In a stack of books, you can only see the top book
If you want to access any other book, you would first need to remove the books on top of it
The bottom-most book in the stack was put first and can only be removed at the last after all books on top of it have been removed.

PUSH Operation

Push operation refers to inserting an element in the stack. Since there’s only one position at which the new element can be inserted — Top of the stack, the new element is inserted at the top of the stack.

POP Operation

Pop operation refers to the removal of an element. Again, since we only have access to the element at the top of the stack, there’s only one element that we can remove. We just remove the top of the stack. Note: We can also choose to return the value of the popped element back, its completely at the choice of the programmer to implement this.

PEEK Operation

Peek operation allows the user to see the element on the top of the stack. The stack is not modified in any manner in this operation.

isEmpty: Check if stack is empty or not

To prevent performing operations on an empty stack, the programmer is required to internally maintain the size of the stack which will be updated during push and pop operations accordingly. isEmpty[] conventionally returns a boolean value: True if size is 0, else False.

Stack Implementation

As we’ve learned before, Stack is a very useful concept that a good programmer could use to his/her benefit. But can you implement it in your code yet? It's not that difficult once you think about it, let’s walk through its properties and implement them in code.

You should remember one very important thing though →

All operations in the stack must be of O[1] time complexity

We shall be implementing stack in two different ways by changing the underlying container: Array and Linked List.

1. Array Implementation

An array is one of the simplest containers offering random access to users based on indexes. But can we access any element of the stack at any given time? No. That’s why we need to set an index as top and then access only the element at index top.

int stack[10] int top = -1

Here, 10 is a pre-defined capacity of the stack. We can throw a stack overflow error if a user tries to exceed this capacity.

★ The default value for the top is -1, denoting that the stack is empty.

Do we need to store any other parameter for the stack? current size, perhaps? No. We may need to store the capacity of the stack but we don’t need to store the current size. We can know the current size of stack by looking at the value of the top. [How?]

Let us wrap this group of data members in a class

class Stack{ int arr[] int capacity int top }

Let us also create a constructor which initializes capacity and top

Stack[int cap] { capacity = cap top = -1 }

★ You are also required to allocate memory to arr according to the language you use to implement it.

→Now, we need to implement the operations that we generally perform on stacks.

PUSH Operation

What changes are made to the stack when a new element is pushed?

A new element is inserted on top
The value of top increases by 1

▹ What if the stack is filled to its capacity?

We shall check if the stack if full before inserting a new element and throw an error if it is.

Now, let us implement this simply

void push[int item] { if [ top == capacity - 1 ] print[ "Stack overflow!" ] else { arr[top+1] = item top = top + 1 } }

POP Operation

Let’s try one more: Pop[].

What changes are made to the stack internally for a pop operation?

The top element is removed
The value of top is decreased by 1

▹ Can you think of an exception in this case like the one above of stack being full? Ans: The stack can be empty when the pop operation is called

Let’s try implementing it now

void pop[] { if [ isEmpty[] == True ] print[ "Stack is empty!" ] else top = top - 1 }

★ Is decreasing the value of top same as deleting the top element? [Think!]

Peek and isEmpty Operation

Peek and isEmpty are quite simple to implement. We need to steer clear of exceptions though.

int peek[] { if [ isEmpty[] == True ] { print[ "Stack is empty!" ] return -1 } else return arr[top] }bool isEmpty[] { if [ top == -1 ] return True else return False }

2. Linked List Implementation

Before implementing stack with a linked list, let us first try to visualize a stack as a linked list. There are two ends of a linked list: head and tail.

Which end do you think should represent the top of the stack? [Think!]

The top of the stack should be represented by head because otherwise, we would not be able to implement the operations of the stack in O[1] time complexity.

Let us assume that we have used class for linked list

class ListNode{ int val ListNode next }

What should an empty stack look like if implemented with a linked list? Ans: Its head will point to NULL

ListNode head = NULL

Is there any benefit to implementing a stack as linked list compared to arrays? Ans: We do not need to mention the size of the stack beforehand.

→ Although, if you want to implement a limit to prevent excess use, you may need to encapsulate the class ListNode inside some other class along with a data member capacity.

class Stack{ int capacity class ListNode{ int val ListNode next } }

We shall be using just using class ListNode below for simplicity.

→Let us move towards stack operations

PUSH Operation

The same properties hold as above with an added benefit that we need not worry about the stack being full

void push[int item] { ListNode temp = ListNode[item] temp.next = head head = temp }

POP Operation

Properties of linked list relaxed us from checking if the stack is full in push operation. Do they provide any relaxation for exceptions in pop operation? No. We still need to check if the stack is empty.

Since the top is represented by the head in this implementation. How do we delete the first element in a linked list?

Simple, we make the second element as the head.

void pop[] { if [ head == NULL ] print [ "Stack is empty!" ] else head = head.next }

★ You may be required to deallocate the popped node to avoid memory leak according to your programming language's conventions.

Peek and isEmpty Operation

The implementation of these two operations is pretty simple and straight-forward in the linked list too.

int peek[] { if [ head == NULL ] { print [ "Stack is empty!" ] return -1 } else return head.val }bool isEmpty[] { if [ head == NULL ] return True else return False }

Augmentations in Stack

You can augment the stack data structure according to your needs. You can implement some extra operations like:-

isFull[]: tells you if the stack if filled to its capacity
The pop operation could return the element being deleted

★ A quite interesting augmentation that has been asked in many interviews asks you to implement a MinStack which holds all properties of a regular stack but also returns the minimum value in the stack. Since all stack operations are expected to be executed in constant time, you need to return the minimum element in the stack in O[1] time complexity.

Applications of Stack Data Structure

An "undo" mechanism in text editors
Forward and backward feature in web browsers
Check for balanced parentheses in an expression
Expression evaluation and syntax parsing
Backtracking. This is a process when you need to access the most recent data element in a series of elements. Think of a maze - how do you find a way from an entrance to an exit? Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point, you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack.
We use a stack for the Iterative implementation of several recursive programs like tree traversals, DFS traversal in a graph, etc.
For solving several problems in algorithms, we use a stack as the principle data structure with which they organize their information.
Memory management: Any modern computer environment uses a stack as the primary memory management model for a running program.

AfterAcademy Data Structure And Algorithms Online Course - Admissions Open

Data Structure and Algorithms - Stack

Stack in Python

A stack is a linear data structure that stores items in a Last-In/First-Out [LIFO] or First-In/Last-Out [FILO] manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.

The functions associated with stack are:

empty[] – Returns whether the stack is empty – Time Complexity: O[1]
size[] – Returns the size of the stack – Time Complexity: O[1]
top[] – Returns a reference to the topmost element of the stack – Time Complexity: O[1]
push[a] – Inserts the element ‘a’ at the top of the stack – Time Complexity: O[1]
pop[] – Deletes the topmost element of the stack – Time Complexity: O[1]

Design a stack that supports getMin[] in O[1] time and O[1] extra space

Question: Design a Data Structure SpecialStack that supports all the stack operations like push[], pop[], isEmpty[], isFull[] and an additional operation getMin[] which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O[1]. To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.
Example:

Consider the following SpecialStack 16 --> TOP 15 29 19 18 When getMin[] is called it should return 15, which is the minimum element in the current stack. If we do pop two times on stack, the stack becomes 29 --> TOP 19 18 When getMin[] is called, it should return 18 which is the minimum in the current stack.

How to use the Stack class in Java

The Stack data structure is based on the Last In First Out [LIFO] principle and in Java, it implements the Java List interface.

The basic operations supported by a stack are push and pop.

Push adds an element at the top of a stack.

1 of 3

Pop removes the topmost element of a stack.

1 of 3

What is a Stack?

A Stack is a linear data structure that follows the LIFO [Last-In-First-Out] principle. Stack has one end, whereas the Queue has two ends [front and rear]. It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.

Some key points related to stack

It is called as stack because it behaves like a real-world stack, piles of books, etc.
A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.
It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.

Working of Stack

Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full.

Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the top to the bottom when we were entering the new element in the stack. The stack gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 5 is entered first, so it will be removed only after the deletion of all the other elements.

Standard Stack Operations

The following are some common operations implemented on the stack:

push[]: When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
pop[]: When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
isEmpty[]: It determines whether the stack is empty or not.
isFull[]: It determines whether the stack is full or not.'
peek[]: It returns the element at the given position.
count[]: It returns the total number of elements available in a stack.
change[]: It changes the element at the given position.
display[]: It prints all the elements available in the stack.

PUSH operation

The steps involved in the PUSH operation is given below:

Before inserting an element in a stack, we check whether the stack is full.
If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:

Before deleting the element from the stack, we check whether the stack is empty.
If we try to delete the element from the empty stack, then the underflow condition occurs.
If the stack is not empty, we first access the element which is pointed by the top
Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Applications of Stack

The following are the applications of the stack:

Balancing of symbols: Stack is used for balancing a symbol. For example, we have the following program:

As we know, each program has an opening and closing braces; when the opening braces come, we push the braces in a stack, and when the closing braces appear, we pop the opening braces from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it means that some syntax occurs in a program.

String reversal: Stack is also used for reversing a string. For example, we want to reverse a "javaTpoint" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null character.
After pushing all the characters, we start taking out the character one by one until we reach the bottom of the stack.
UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There would be two stacks in which one stack shows UNDO state, and the other shows REDO state.
If we want to perform UNDO operation, and want to achieve 'ab' state, then we implement pop operation.
Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.
DFS[Depth First Search]: This search is implemented on a Graph, and Graph uses the stack data structure.
Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a particular path, and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path, we have to use the stack data structure.
Expression conversion: Stack can also be used for expression conversion. This is one of the most important applications of stack. The list of the expression conversion is given below:Infix to prefix Infix to postfix Prefix to infix Prefix to postfix Postfix to infix
Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks. The memory is known as stack memory as all the variables are assigned in a function call stack memory. The memory size assigned to the program is known to the compiler. When the function is created, all its variables are assigned in the stack memory. When the function completed its execution, all the variables assigned in the stack are released.

Next TopicDS Array Implementation Stack

← prev next →