Data Structures and Algorithms Using Python

A stack is a very important data structure. We find its application in various situations in computer science. In this chapter we will discuss the operations related to stacks, how a stack is represented in memory, various areas of applications where stacks are used, etc.

8.1 Definitions and Concept

A stack is a linear data structure in which both insertion and deletion operations occur only at one end. The insertion operation is commonly known as PUSH and the deletion operation is known as POP. As both the operations occur at one end, when the elements are pushed into a stack the elements are stored one after another and when the elements are popped only the topmost element can be removed first and then the next element gets the scope to be popped. In real life also we can see various analogies of this structure, such as a stack of coins, stack of plates, stack of boxes, etc. (Figure 8.1). Suppose, in a stack of coins, if we want to place a new coin, it should be placed at the top of the stack, and if we want to get a coin from that stack, we should remove the topmost coin from the stack. Since in a stack always the element that was inserted last is removed first, it is known as a LIFO (Last In First Out) data structure.

8.2 Operations Associated with Stacks

The basic operations related to a stack are the following:.

• • Push: Insert an element into a stack.

• • Pop: Retrieve an element from a stack.

Apart from these two basic operations, to use a stack efficiently we need to add the following functionalities:

• • Peek: Get the top element of the stack without removing it.

• • Isempty: To check whether the stack is empty or not.

• • Isfull: To check whether the stack is full or not.

All these operations execute with the time complexity O(1).

In some situations we need to check the top element without removing it. That is why the peek operation is required. Again, if a stack is full, the push operation cannot be done on the stack. Similarly, pop and peek operations cannot be performed on an empty stack. Thus, before these operations we need to check whether the stack is full or empty.