Understanding Stacks, Queues, and Abstract Data Types

Suppose you are writing a program that must keep a list of names in alphabetical order. You need to add names, remove names, and check whether a name is present. A natural first question is where the names should live in memory and how the list should be arranged internally. This article asks a different question first: what exactly is the list, apart from the way it happens to be stored?

Keep that question in mind as you read. The answer leads to a central idea in software engineering, the abstract data type, usually written ADT. Once you see what an ADT is, you will also see why the same list of names can be stored in very different ways without changing the rest of the program.

Notice what this reasoning did not require. You could carry out every step on paper with a pencil and a sheet of names. You did not decide whether the names sit in a fixed block or a chain of linked objects, and you did not decide how insert moves items internally. That separation is deliberate, and the rest of the article builds on it.

The definition has two halves, and both matter. The first half names the values the type can take. The second half names the operations that act on those values. The definition is silent on everything else. It does not say whether the values sit in a chain of linked objects, in a fixed-size block, or somewhere else. It does not say how an operation works internally. It describes only what is possible and what can be done with it.

For the ordered list of strings, the set of values is every sequence of strings arranged in increasing order. The operations are inserting a new string, deleting a string, and finding a string in the list. Nothing in that description mentions arrays, linked objects, or pointers. Those details belong to a later decision, the implementation.

A linked list is a particular type of data structure, made up of objects linked together by pointers. Earlier, a linked list was used to store the ordered list of strings, and insert, delete, and find were implemented on that list. The source makes a striking observation: the same list could just as easily have been stored in an array or an ArrayList, and the same operations could still have been implemented on it.

The diagram below shows the same three names held in two representations. On the top row the names occupy numbered slots side by side, as in a contiguous array. On the bottom row each name sits in its own node, and each node points to the next one, as in a linked structure. The logical list is identical in both rows.

The implementations differ on the inside. An array-based insert and a linked-list insert do not work the same way: one may need to shift elements to make room, while the other rewires pointers between nodes. Yet their interfaces and their logical behavior stay the same. Callers still ask for an insert, and the list still ends up in the same order. This is the core of what makes an ADT useful: one abstract type can have several implementations.

The source describes this idea as data abstraction: separating the interface of a data structure from its implementation. The interface is the set of operations a caller can use, along with their logical behavior. The implementation is the concrete way those operations are carried out. Data abstraction keeps these two apart on purpose.

The diagram below reads from top to bottom. The calling program depends on the interface and nothing lower. The two implementations sit beneath the interface, and either one can fill the role. Because the arrow from the program stops at the interface, a change to the storage below it does not reach the program.

Think about the consequence. If a team writes its program against the abstract definition, switching the storage later is a change confined to the implementation. The rest of the program is untouched. The source states this directly: changing the implementation of an ADT does not affect the program as a whole, and this can make programs easier to debug and maintain.

A stack follows a last-in, first-out rule, usually abbreviated LIFO. Its main operations are push, which adds an element, and pop, which removes the most recently added element. A queue follows a first-in, first-out rule, abbreviated FIFO. Its main operations are enqueue, which adds an element at the back, and dequeue, which removes the element that has waited longest.