What is the earliest implementation of the stack data structure in C? [closed]

Question

I am trying to find the source code for the earliest implementation of the stack data structure in C, but I can't find anything.

I am particularly interested in knowing if the member variables of the stack data structure were made private, or if they were kept public (and so it was the job of the programmer not to modify these variables by accident).

Note: If the source code for the stack data structure is not available, I am also interested in the source codes of other data structures like queue and linked list and so on.

Answer 1

I am trying to find the source code for the earliest implementation of the stack data structure in C

There is no stack data structure in C. Look through the language specification and you won't find it there. If you were a programmer and you wanted a stack, you had to implement your own. If you go back to the beginnings of C and look at all the code that needed a stack, you'll probably find that there were as many implementations as there were stacks.

There are many ways to implement a stack in C. Perhaps the easiest is as an array and an index

int intStack[STACK_SIZE];
int stackPointer = 0;

void push(int newElement) 
{
    intStack[stackPointer++] = newElement;
}

int pop() 
{
    return intStack[--stackPointer];
}

Two points about the above:

1. I'm using modern syntax. I can barely remember how to write K&R C, so I'm not even going to try.
2. There are no checks for stack overflow or underflow. It would complicate the code and there were probably plenty of stacks written without bounds checks anyway.

The above implementation is very similar to a stack defined in K&R The C Programming Language in chapter 4 which probably counts as a fairly early example of a stack.

I am particularly interested in knowing if the member variables of the stack data structure were made private, or if they were kept public

That would depend on the quality of the programmer. Contrary to popular belief, C does have data hiding. In fact, I would argue that it is better than C++¹. However, there's no qualification of structure members by access keywords. Data hiding has to be done at the compilation unit (file) level and is all or nothing. Here's how:

Firstly, you need to put the elements of your stack and the pointer into a struct in a separate source file.

/* intstack.c */

#include "intstack.h" /* See below for what is in here */

struct IntStack
{
    int data[STACK_SIZE];
    int pointer;
}

void IntStack_push(struct IntStack *stack, int newElement) 
{
    stack->data[stack->pointer++] = newElement;
}

int IntStack_pop(struct IntStack *stack) 
{
    return stack->data[--stack->pointer];
}

struct IntStack *IntStack_new()
{
    return calloc(1, sizeof(struct IntStack));
} 

void IntStack_delete(struct IntStack *stack)
{
    free(stack);
}

Then you need a header file that has prototypes of all the functions and an incomplete declaration of the struct

/* intstack.h */

struct IntStack; /* Incompleter declaration */

void IntStack_push(struct IntStack *stack, int newElement); 

int IntStack_pop(struct IntStack *stack); 

struct IntStack *IntStack_new();

void IntStack_delete(struct IntStack *stack);

Other people can use your stack by simply including the header file. They have no access to the internal members of the struct (well, not without doing something bad casting pointers to the struct to some other type).

#include "intstack.h"

int main()
{
    struct IntStack *stack = IntStack_new();

    IntStack_push(stack, 3);
    printf("%d\n", IntStack_pop()); /* prints 3 */
    IntStack_delete(stack);

    return 0;
}

I am also interested in the source codes of other data structures like queue and linked list and so on.

Similar comments to the above are applicable². Incidentally, a singly linked list is pretty much the same as a dynamically growing stack i.e. one that doesn't overflow until the memory runs out.

---

¹ In C++ you haver to put the private members in a class declaration in a header which means the protections can be defeated simply by #define private public before the header is included.

² Some operating systems have implementations of queues e.g. macOS has a number of library functions and macros to implement queues of various types.

Answer 2

As mentioned in the comments, data can’t be entirely hidden in C, there is no concept of “public” v. “private” members of data structures. Members can be hidden in practice using pointers to opaque data structures (see for example FILE), but that’s only a “gentleman’s agreement”.

When looking for early implementations in C, your best bet is to dig in the early Unix code. For example, here’s an early linked list (Research V4, August 1973):

struct cblock {
    struct cblock *c_next;
    char info[6];
};

The same release already had dc, which manipulates a stack, but it was written in assembly; its C implementation in V7 (1979) has a stack, although it’s probably not the earliest implementation of a stack in C:

struct  blk *stack[STKSZ];
struct  blk **stkptr,**stkbeg;
struct  blk **stkend;
int stkerr;

In fact an earlier implementation can be seen in the C compiler in V6 (1975):

    struct tnode *expstack[20];
    register struct tnode **sp;

As is commonly the case in C, the stack isn’t implemented as an explicit data structure (struct), but as an array and a pointer, with bounds-checking (albeit after-the-fact in this case).

Answer 3

My understanding is that the stack is provided at the architectural level, eg it is built in to the processor in the form of a stack pointer and relevant operators. It is not a language level concept, in the way that other data structures may be.

Answer 4

I'm probably repeating other posts, but let me try and summarize.

1. There is no 'stack' in the definition of the C language

2. An implementation of C very likely uses a stack for activation records (holding local variables and return addresses, for example) -- also known as a 'call stack'.

3. The C standard library has no 'stack' data structure

4. The concept of 'stack' is much older than C (and older than settling on the word 'stack' as the name to use)

5. There were surely countless private implementations of a stack structure in C; it's so simple.